Geometric comparison

  • Mytaxi, Daimler: How similar are our routes vs. Google?

-Need reliable way to measure this!

Methodology

  • Review state-of-the-art
  • Create synthetic test cases (controlled outcome)
  • Test algorithms for:
    1. Meaningfulness
    2. Performance

Synthetic test cases

  • Emulate common challenging scenarios
    • Detours
    • Very short/long route sensitivity
    • Noise (trace vs match)
    • Shifts (different maps)
    • Sparseness (different sampling)
  • Control the desired outcome
  • Total of 39 synthetic tests

Scenarios: basic

Test common and basic scenarios.

In [2]:
render_basic_scenarios()

Scenarios: detours

Test sensitivity to detour severity

In [3]:
render_detours()

Scenarios: shifts

Test resiliance to shifted maps.

In [4]:
render_shifts()

Scenarios: noise

Test resiliance to noisy data (e.g. suitability as match success classifier)

In [5]:
render_noisy()

Scenarios: subsampling

Test resiliance to subsampled routes

In [6]:
render_sparse()

Scenario: start/end point mismatch

Test resiliance to start/end point mismatch

In [7]:
render_start_end_mismatch()

Algorithms

Approaches:

approach "detour" sensitivity "bias" sensitivity range speed examples
distance high low 0-inf slow/fast Hausdorff, Frechet, centroids
area low high 0-inf fast AUC
correlation medium medium 0-100% slow/fast AUC normalized, CIR, CPR
hybrid high high 0-inf slow BOC
  • detour sensitivity: whether it captures occasional, well pronnounced differences
  • bias sensitivity: whether it captures systemic, small differences

Hausdorff distance

Maximum of minimum distance possible between any two pairs of points of the geometry.

https://en.wikipedia.org/wiki/Hausdorff_distance

In [8]:
Image('_img/hausdorff.png', embed=True)
Out[8]:

Frechet distance

The Fréchet distance is a measure of similarity between curves that takes into account the location and ordering of the points along the curves.

https://en.wikipedia.org/wiki/Fréchet_distance

In [9]:
Image('_img/frechet.png', embed=True, width=500)
Out[9]:

Dynamic Time Warping

Compares phased-in geometry/sequence distance.

https://en.wikipedia.org/wiki/Dynamic_time_warping

In [10]:
Image('_img/dtw.png', embed=True, width=300)
Out[10]:

Centroid distance

Calculates distance between geometry centroids/centers-of-mass

In [11]:
l1 = test_detour_big_very_short_1.to_linestring(convert_to_utm=True)
l2 = test_detour_big_very_short_2.to_linestring(convert_to_utm=True)
plt.plot(*zip(*l1.coords))
plt.plot(*zip(*l2.coords))
plt.scatter(l1.centroid.x, l1.centroid.y)
plt.scatter(l2.centroid.x, l2.centroid.y)
Out[11]:
<matplotlib.collections.PathCollection at 0x7f5b557e3d30>

AUC

Calculates area defined between the two geometries/curves.

In [12]:
utm_linestring_1 = test_detour_big_very_short_1.to_linestring(convert_to_utm=True)
utm_linestring_2 = test_detour_big_very_short_2.to_linestring(convert_to_utm=True)
sg.Polygon(list(utm_linestring_1.coords) + list(utm_linestring_2.coords)[::-1])
Out[12]:

AUC normalized

Calculates area defined between the two geometries/curves and normalizes it by envelope containing both geometries.

In [2]:
utm_linestring_1 = test_detour_big_very_short_1.to_linestring(convert_to_utm=True)
utm_linestring_2 = test_detour_big_very_short_2.to_linestring(convert_to_utm=True)
polygon = sg.Polygon(list(utm_linestring_1.coords) + list(utm_linestring_2.coords)[::-1])
plt.plot(*zip(*list(polygon.envelope.boundary.coords)))
plt.plot(*zip(*list(polygon.boundary.coords)))
Out[2]:
[<matplotlib.lines.Line2D at 0x7f0c000ed780>]

BOCS (Bias-Outlier Composite Score)

Geometric mean of max distance and total AUC.

In [3]:
l1 = test_detour_big_very_short_1.to_linestring(convert_to_utm=True)
l2 = test_detour_big_very_short_2.to_linestring(convert_to_utm=True)
plt.plot(*zip(*l1.coords))
plt.plot(*zip(*l2.coords))
plt.scatter(l1.centroid.x, l1.centroid.y)
plt.scatter(l2.coords[13][0] + 85, l2.coords[13][1] - 28)
Out[3]:
<matplotlib.collections.PathCollection at 0x7f0bbcabf940>

PMR (Point Match Ratio)

% of points close enough to other geometry

In [7]:
corridor_1 = utm_linestring_1.buffer(10)
corridor_2 = utm_linestring_2.buffer(10)

display('All points:')
display(corridor_1.union(corridor_2))
display('Point matches:')
display(corridor_1.intersection(corridor_2))
'All points:'
'Point matches:'

Levenshtein (edit) distance

Minimum number of edits required to transform encoded polyline of one to the other.

In [8]:
Image('_img/levensthein.png', embed=True, width=400)
Out[8]:

Results

Accuracy in synthetic tests

In [10]:
configs = {
    'hausdorff': {'name': 'hausdorff', 'params': {}},    
    # TOO SLOW 'frechet': {'name': 'frechet', 'params': {}}, 
    # TOO SLOW 'dtw': {'name': 'dtw', 'params': {}},
    'centroids': {'name': 'centroids', 'params': {}},
    'auc': {'name': 'auc', 'params': {}},
    'auc_norm': {'name': 'auc', 'params': {'normalized': True}},
    'bocs': {'name': 'bocs', 'params': {}},
    'pmr': {'name': 'pmr', 'params': {}},
    'pmr_lenient': {'name': 'pmr', 'params': {'buffer': 50}},
    'pmr_strict': {'name': 'pmr', 'params': {'buffer': 3}},
    'levensthein': {'name': 'levenshtein', 'params': {}},
}

tests = sorted(glob.glob('data/*.json'))
results = run_tests(tests, configs)
df = pd.DataFrame(results).transpose()

Score correlation:

In [11]:
sns.heatmap(df.corr())
Out[11]:
<matplotlib.axes._subplots.AxesSubplot at 0x7f0bbc54b390>

Accuracy in real world cases

100 tests, Berlin coverage map:

In [100]:
results_df = pd.read_csv('results/routes_comparison.csv')
plot_all(results_df)

Results:

In [94]:
create_debug_artifacts(results_df)
/home/pedro/.local/share/virtualenvs/route-quality-u_irGnMv/lib/python3.7/site-packages/matplotlib/cbook/deprecation.py:107: MatplotlibDeprecationWarning: Adding an axes using the same arguments as a previous axes currently reuses the earlier instance.  In a future version, a new instance will always be created and returned.  Meanwhile, this warning can be suppressed, and the future behavior ensured, by passing a unique label to each axes instance.
  warnings.warn(message, mplDeprecation, stacklevel=1)

Conclusions

  • PMR most meaningful when comparing to others
    • Ratio is much more understandable
    • Does not capture severity of differences
  • Hausdorff best candidate for binary classifier:
    • Are both routes the same?
    • Determine match success

Code

Package: route_quality.metrics.geometry

Script: geometry-comparison.py

in https://gitlab.mobilityservices.io/am/roam/route-quality

Next

  • Find accuracy of prime metrics as match success classifiers
  • Continue evaluating different metrics for different purposes

Preliminary tests

In [15]:
analyze_results()
score_compare_hausdorff score_compare_cir score_compare_pmr
count 100.000000 100.000000 100.000000
mean 700.722069 0.567035 0.711785
std 896.430325 0.277168 0.277051
min 4.388269 0.000950 0.004310
25% 145.836679 0.347873 0.546644
50% 466.416557 0.646440 0.791475
75% 830.610520 0.814544 0.944706
max 4937.005377 0.932101 1.000000

Bonus: Route stats

Length comparison

In [394]:
compare_distributions(metrics, 'length', 'Length [km]', palette=palette)

ETA comparison

In [396]:
compare_distributions(metrics, 'eta', 'ETA [min]', palette=palette)

Speed comparison

In [397]:
compare_distributions(metrics, 'speed', 'Speed [km/h]', palette=palette)

Speed diffs vs Google

In [398]:
df['das-traffic'] = df['speed_das-traffic'] - df['speed_google']
df['das'] = df['speed_das'] - df['speed_google']
vs = pd.melt(df[['route_id', 'das-traffic', 'das']], id_vars=['route_id'], var_name='provider', value_vars=['das-traffic', 'das'], value_name='speed_diff')
compare_distributions(vs, 'speed_diff', 'Speed diff. to Google [km/h]', palette=palette)

ETA vs Length

In [404]:
f = plt.figure()
sns.lmplot(data=metrics.drop(index=24).sort_values('speed', ascending=True), 
           x='length', y='eta', hue='provider', palette=palette, markers='.')
plt.xlabel('Duration [km]')
plt.ylabel('ETA [min]')
Out[404]:
Text(31.5515,0.5,'ETA [min]')
<Figure size 432x288 with 0 Axes>